/*
The counting algorithm is O(n), but the input element cannot > k. The size of input should be small
*/

#include <iostream>
using namespace std;

const int minInt = -2147483648;
const int len=8;

int find_largest(int *A)
{
	int i;
	int max = A[1];
	for(i=2;i<len+1;i++)
	{
		if(max<A[i])
		{
			max = A[i];
		}		
	}
	return max;	
}

int *count_sort(int *A)
{
	int i;

	// Find the biggest element.
	int max = find_largest(A);

	// Create C to record how many integers in A that > A[i];
	int *C = new int[max+1];
	
	// Create B to record the result.
	int *B = new int[len];

	// Initialize C
	for(i=0;i<max+1;i++)
		C[i] = 0;
	// Calculate how many C[i] times appers in A 
	i=1;
	for(i=1;i<len+1;i++)
		C[A[i]]++;
	
	// Calculate how many elements of A are > C[A[i]]
	i=0;
	for(i=1;i<max+1;i++)
		C[i] = C[i] + C[i-1];	
	
	// Assign these elements of A into proper posisiton in B
	i=1;
	for(i=1;i<len+1;i++)
	{
		B[C[A[i]]] = A[i];
		C[A[i]]--;
	}

	//test
	i=0;
	cout << "C: ";
	for(i=0;i<max+1;i++)
		cout << C[i] << " ";
	cout << endl;

	return B;
}

int main()
{

	int A[9] = {minInt,2,5,3,0,2,3,0,3};

	int *B = count_sort(A);

	int i;
	cout << "B:" ;
	for(i=1;i<9;i++)
	{
		cout << B[i]<<" ";
	}
	cout << endl;
	return 0;
}
